package com.coder.algorithm.offer_2;

import java.util.Arrays;
import java.util.Locale;

/**
 * 数组中的逆序对
 *
 * @author yuhushuan
 * @date 2020/6/29 00:18
 */
public class _51_1_InversePairs {

    private static int inversePairs(int[] array) {
        if (array == null) {
            return 0;
        }
        int[] copy = new int[array.length];
        int count = inversePairsCore(array, copy, 0, array.length - 1);
        return count;
    }

    private static int inversePairsCore(int[] array, int[] copy, int start, int end) {
        if (start == end) {
            copy[start] = array[start];
            return 0;
        }

        int mid = (start + end) >> 1;
        int leftStart = start;
        int leftEnd = mid;
        int rightStart = mid + 1;
        int rightEnd = end;

        int left = inversePairsCore(array, copy, leftStart, leftEnd);
        int right = inversePairsCore(array, copy, rightStart, rightEnd);
        int count = 0;

        int index = end;
        while (leftStart <= leftEnd && rightStart <= rightEnd) {
            if (array[leftEnd] > array[rightEnd]) {
                copy[index--] = array[leftEnd--];
                count += rightEnd - rightStart + 1;
            } else {
                copy[index--] = array[rightEnd--];
            }
        }
        while (leftStart <= leftEnd) {
            copy[index--] = array[leftEnd--];
        }
        while (rightStart <= rightEnd) {
            copy[index--] = array[rightEnd--];
        }
        for (int i = start; i <= end; ++i) {
            array[i] = copy[i];
        }
        return left + right + count;
    }

    public static void main(String[] args) {
        // 功能测试
        // 未经排序
        print(new int[]{7, 5, 6, 4});
        // 递增排序
        print(new int[]{2, 4, 6, 8, 10});
        // 递减排序
        print(new int[]{5, 4, 3, 2, 1});
        // 包含重复数字
        print(new int[]{8, 4, 6, 4});

        // 边界值测试
        // 只有两个数字
        print(new int[]{2, 1});
        print(new int[]{2});

        // 特殊输入测试
        print(null);
    }

    private static void print(int[] array) {
        System.out.println(String.format(Locale.getDefault(),
                "数组：%s",
                Arrays.toString(array)));

        System.out.println(String.format(Locale.getDefault(),
                "存在 %d 个逆序对\n",
                inversePairs(array)));


    }
}
